#!/usr/bin/env python
# -*- coding:UTF-8 _*_
"""
@Project:gnn_demo-master
@File:heapSort.py
@IDE:PyCharm
@Author:cuixinhong
@Date:2022/4/24 20:14
"""
class Solution:
    def getLeastNumbers(self, arr, k) :
        if k > len(arr) or k == 0:
            return []
        n = len(arr)
        a = arr[:k]
        # 维护一个堆使其成为大顶堆
        #range(a,b,-1)意思是从列表的下标为a的元素开始，倒序取到下标为b的元素，但是不包括下标为b的元素
        for i in range(k//2-1, -1, -1):
            self.initiate(i, a, k)
        # 遍历剩下的n-k个数，判断是否要添加进堆中
        for i in range(k, n):
            if arr[i] < a[0]:
                a[0] = arr[i]
                self.initiate(0, a, k)
        # 将最后得到的大顶堆进行排序
        for i in range(len(a)-1, -1, -1):
            a[i], a[0] = a[0], a[i]
            self.initiate(0, a, i)
        return a

    def initiate(self, index, a, length):
        temp = a[index]
        j = index*2+1
        while j < length:
            if j+1 < length and a[j+1] > a[j]:
                j += 1
            if a[j] > temp:
                a[index] = a[j]
                index = j
            else:
                break
            j = j*2+1
        a[index] = temp
if __name__ == '__main__':
    arr=[4,5,1,6,2,7,3,8]
    s=Solution()
    print(s.getLeastNumbers(arr,4))
